1. Field of the Invention
The present invention relates to a curve generator for a display system, to a display system including such a generator and to methods of generating curves in a display system.
2. Background Art
To generate curves such as an arc of a circle from data defining the arc is a non-trivial task in a computer due to the significant calculations involved.
A circle centered at the origin of a coordinate system can be defined by the following, well known, equation: EQU x.sup.2 +y.sup.2 =R.sup.2 ( 1)
where x and y are the variable horizontal and vertical coordinates of the coordinate system, and R is the radius of the circle.
Solving this equation for y gives: EQU y=.+-.(R.sup.2 -x.sup.2).sup.1/2 ( 2)
A simple approach to drawing one quadrant of a circle using this equation is to increment x in unit steps from O to R solving for +y at each of the steps. The other three quadrants of the circle can then be determined about the origin using the symmetry of the circle. Although this technique works, it is inefficient because of the multiply and square root operations.
A similarly inefficient method is simply to plot R cos .theta. or R sin .theta. by stepping .theta. from 0.degree. to 90.degree., and then generating the other three quadrants using the symmetry of the circle.
An improved method of generating a circular arc is described in J. E. Bresenham's article "A Linear Algorithm for Incremental Digital Display of Circular Arcs" published on pages 100-106 of "Communications of the ACM", Vol. 20, No. 2, in February 1977. This method, which is based on equation (1) above, was conceived for use with pen plotters, although it is applicable generally to pixel based display systems.
In accordance with the method, points on a circle centered at the origin are generated by stepping round the circle. At each step the pixel point which is closest to the true circle is selected for display by employing an error term: EQU D (Pt.sub.i)=(x.sup.2.sub.i +y.sup.2.sub.i)-R.sup.2 ( 3)
where D(Pt.sub.i) is the difference between the true circle for the ith point (Pt.sub.i) and x.sub.i and y.sub.i are the x and y values calculated for the ith point.
References to these and to many other techniques can be found in Foley and Van Dam's book "Fundamentals of Interactive Computer Graphics" (published in 1982 by Addison-Wesley Publishing Company), on pages 442-446.
In theory the prior technique work well, although with varying degrees of efficiency. They are designed essentially to draw complete circles, although they can of course be used to draw an arc of a circle. In practice, however, when implemented in a graphics processing system, severe limitations as to their applicability to the drawing of arcs are encountered. In particular, the prior techniques run into difficulty in accurately plotting an arc which forms part of a very large circle where only part of the circle is within the system coordinate space. This results primarily from the need to compute, either explicitly or implicitly, the actual center of the circle of which the arc forms part. If an arc is to be drawn which is almost a straight line, it will be appreciated that a very large number will be needed to define the radius of circle of which it forms part, as the center of the circle may be well outside the bounds of the coordinate space within which the arcs are to be generated.